
public class Avl {
	private int size;
	AVLNode root;
	
	public Avl(){
		root = null;
		this.size=0;
	}
	
	public void Insert( int key, Object data )
	{
		this.size++;
		if( root == null )
		{	
			root = new AVLNode( key, data);	
		}	
		else
			Insert( key, data, root);
	}
	
	
	private void Insert(int newKey, Object newData, AVLNode node )  //incase not an empty tree
	{
		if( node.key > newKey ){
			if( node.lChild == null )
				node.lChild = new AVLNode( newKey, newData, node);
			else
				Insert( newKey, newData, node.lChild );
		}
		else
		{
			if( node.rChild == null )
				node.rChild = new AVLNode( newKey, newData, node);
			else
				Insert( newKey, newData, node.rChild);
		}
		
		checkAVL(node);
	}
	
	public void checkAVL(AVLNode node)
	{
		int lHeight , rHeight;
		lHeight = getHeight(node.lChild);
		rHeight = getHeight(node.rChild);
		if( Math.abs( lHeight - rHeight ) <= 1 ) 	//The AVL property holds	
		{
			node.height = Math.max( lHeight, rHeight ) + 1;
		}
		
		else 										//The AVL property has been violated - a fix is needed
			fixAVL( node, lHeight, rHeight );
	}
	
	public int getHeight( AVLNode n){
		if( n == null )
			return -1;
		else
			return n.height;
	}

	private void replaceChild(AVLNode node, AVLNode curChild, AVLNode newChild)
	{
		if(node.lChild == curChild)
			node.lChild = newChild;
		else if(node.rChild == curChild)
			node.rChild = newChild;
		if(newChild != null)
		{
			newChild.parent = node;
			newChild.setHeight();
		}
			node.setHeight();
	}
	
	private void leftRotation(AVLNode a){
		AVLNode b = a.rChild;
		if (a.parent!=null)
			replaceChild(a.parent, a, b);
		else
		{
			root = b;
			b.parent = null;
		}
		replaceChild(a, a.rChild, b.lChild);
		b.lChild = a;
		a.parent = b;
		a.setHeight();
		b.setHeight();
		}


	private void rightRotation(AVLNode a){
		AVLNode b = a.lChild;
		if (a.parent!=null)
			replaceChild(a.parent, a, b);
		else
		{
			root = b;
			b.parent = null;
		}
		replaceChild(a, a.lChild, b.rChild);
		b.rChild = a;
		a.parent = b;
		a.setHeight();
		b.setHeight();
	}
	
	private void fixAVL(AVLNode node, int lHeight, int rHeight )
	{
		if( lHeight > rHeight ) //The balance tips to the left
		{ 
			if( getHeight( node.lChild.lChild ) > getHeight( node.lChild.rChild ) ) //case 1 - rotation right
			{
				rightRotation(node);
			}
			else if( getHeight( node.lChild.lChild ) < getHeight( node.lChild.rChild ) ) //case 2 - double rotation left-right
			{
				leftRotation(node.lChild);
				rightRotation(node);
			}
		}
		
		if( rHeight > lHeight ) //The balance tips to the right
		{
			if( getHeight( node.rChild.rChild ) > getHeight( node.rChild.lChild ) ) //case 1 - rotation left
			{
				leftRotation(node);
			}
			else if( getHeight( node.rChild.rChild ) < getHeight( node.rChild.lChild ) ) //case 4 - double rotation right-left
			{
				rightRotation(node.rChild);
				leftRotation(node);
			}
		}
	}
	
	
	
	
	
	public int Search(int id) {
		if(root==null)
			return -1;		//checked the root and was not found (because tree doesnt exist)
		else
			return root.Search(id,1);		////return the tree check plus the hash table cell check 
	}

	public int getSize() {
		return size;
	}
	
	public int getAVLHeight()
	{
		if(size==0)
			return 0;
		else
			return (int)(Math.log(size)/Math.log(2))+1;
	}
	

}
